\documentclass[11pt,xcolor=dvipsnames]{beamer}

\usecolortheme[named=Blue]{structure}

\usetheme[height=7mm]{Rochester} 
\setbeamertemplate{items}[ball] 
\setbeamertemplate{blocks}[rounded][shadow=true] 

\usepackage[portuges,brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{ae,aecompl}
\usepackage[T1]{fontenc}
\usepackage{algorithm}
\usepackage[noend]{algorithmic}
\usepackage{subfigure}
\usepackage{graphics}
\usepackage{epstopdf}

\usepackage{amsmath,amssymb}
\usepackage{color}
\usepackage{isorot}

\algsetup{linenosize=\scriptsize}
\algsetup{indent=18pt}

\newenvironment{changemargin}[2]{%
\begin{list}{}{%
\setlength{\topsep}{0pt}%
\setlength{\leftmargin}{#1}%
\setlength{\rightmargin}{#2}%
\setlength{\listparindent}{\parindent}%
\setlength{\itemindent}{\parindent}%
\setlength{\parsep}{\parskip}%
}%
\item[]}{\end{list}}

\setbeamercovered{dynamic}

\setbeamertemplate{items}[default]

\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{footline}[page number] 

\title{Making Heuristics Faster with Data Mining}
\institute[UFF]{Universidade Federal Fluminense, Niter\'oi-RJ\\Instituto de Computa\c c\~ao}
\author{Daniel Martins\\~~\\Orientadores:\\Alexandre Plastino\\Simone Martins\\
Isabel Rosseti}
\date{dezembro de 2011}


\AtBeginSection[]{\frame{\frametitle{Sum\'ario}\tableofcontents[current]}}

\begin{document}

\frame{
%\frametitle{XXLIII Simp\'osio Brasileiro de Pesquisa Operacional}
%\includegraphics<1>[width=.25\textwidth]{logoic.eps}
\titlepage}

\part{Main Part}
\frame{\frametitle{Sum\'ario}\tableofcontents[part=1]}


\section{Introdu\c c\~ao}

\begin{frame}
\frametitle{Objetivo}
\begin{itemize}
\item Introduzir um procedimento de Minera\c c\~ao de Dados em uma heur\'istica do estado da arte do problema das p-Medianas\\~~\\
\item Obter com essa nova heur\'istica solu\c c\~oes de qualidade similar ou superior em menor tempo computacional 
\end{itemize}

\end{frame}
  
\begin{frame}  
\frametitle{Conceitos}

\begin{itemize}
\item Metaheur\'{\i}sticas:
\begin{itemize}
\item Resolver de forma aproximada problemas de
otimiza\c c\~ao combinat\'oria.
\end{itemize}
\end{itemize}

\begin{itemize}
\item GRASP (Greedy Randomized Adaptive Search Procedures):
\begin{itemize}
\item Metaheur\'{\i}stica iterativa, onde cada itera\c c\~ao \'e
composta de duas fases: constru\c c\~ao e busca local.
\end{itemize}
\end{itemize}

\begin{itemize}
\item Minera\c c\~ao de Dados:
\begin{itemize}
\item Extrair conhecimento de uma base de dados.
\end{itemize}
\end{itemize}

\end{frame}  

\begin{frame}  
\frametitle{Problema das p-Medianas}
\begin{itemize}
\item {Dados:\\Conjunto $F$ de $m$ potenciais instala\c c\~oes \\
Conjunto $U$ de $n$ clientes\\
Fun\c c\~ao de dist\^ancia $d: U \times F \rightarrow \mathbb{R}$\\
constante p \leq m\\}
\end{itemize}
\begin{itemize}
\item {Determinar:\\ $p$ instala\c c\~oes de modo a minimizar a soma das dist\^ancias de cada cliente \`a sua instala\c c\~ao mais pr\'oxima}
\end{itemize}

\end{frame}  

\begin{frame}  
\frametitle{Problema das p-Medianas}
\begin{columns}[c]
\column{.85\textwidth}
\begin{figure}[ht]
\centering
\includegraphics[width=\textwidth]{pmed.pdf}
\label{fig:graspcusto}
\end{figure}
\column{.15\textwidth}
\begin{block}{~~\\}
n=9\\m=3\\p=2
\end{block}
\end{columns}
\end{frame}  

\begin{frame}  
\frametitle{GRASP}
GRASP\\~~\\
\begin{itemize}
\item Uma itera\c c\~ao do GRASP:
\begin{itemize}
\item Construir uma solu\c c\~ao vi\'avel.
\end{itemize}
\begin{itemize}
\item Usar a busca local para melhorar a solu\c c\~ao constru\'{\i}da.
\end{itemize}
\begin{itemize}
\item Atualizar a melhor solu\c c\~ao encontrada.
\end{itemize}
\end{itemize}

\end{frame}  

\begin{frame}  
\frametitle{Path Relinking}
\begin{itemize}
\item Reconex\~oes por caminhos:
\begin{itemize}
\item Explora trajet\'orias que conectam boas solu\c c\~oes.
\end{itemize}
\end{itemize}

\hspace*{5cm}
\begin{figure}[ht]
\centering
\includegraphics[width=.750\textwidth]{figura_pr.png}
\label{fig:graspcusto}
\end{figure}

\end{frame}  

%\begin{frame}  
%\frametitle{Algor\'{\i}timo}

%\begin{itemize}
%\item GRASP-PR
%\begin{itemize}
%\item Construir uma solu\c c\~ao vi\'avel.
%\end{itemize}
%\begin{itemize}
%\item Usar a busca local para melhorar a solu\c c\~ao constru\'{\i}da.
%\end{itemize}
%\begin{itemize}
%\item \bf{Aplicar reconex\~ao por caminhos para melhorar a solu\c c\~ao.}
%\end{itemize}
%\begin{itemize}
%\item \bf{Atualizar o conjunto de solu\c c\~oes elite.}
%\end{itemize}
%\begin{itemize}
%\item Atualizar a melhor solu\c c\~ao encontrada.
%\end{itemize}
%\end{itemize}

%\end{frame}  


\section{Heur\'istica H\'ibrida Multistart -- HH}

\begin{frame}  
\frametitle{Heur\'istica H\'ibrida Multistart -- HH}

M.~G.~C. Resende and R.~F. Werneck,
{\em A hybrid heuristic for the p-median problem},
Journal of Heuristics 10, pp.~59--88 (2004).\\~~\\

\begin{itemize}
\item $k$ itera\c c\~oes do GRASP com Path Relinking
\begin{itemize}
\item Constru\c c\~ao
\item Busca Local
\item Path Relinking
\end{itemize}
\item P\'os--Otimiza\c c\~ao
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Constru\c c\~ao}
Constru\c c\~ao:\\
\begin{itemize}
\item At\'e completar p instala\c c\~oes:\\
\begin{itemize}
\item Escolhe aleatoriamente $q$ instala\c c\~oes ($q = \lceil log_2(m/p)\rceil$)\\
\item Adiciona \`a solu\c c\~ao a mais lucrativa dessas $q$ instala\c c\~oes
\end{itemize}
~~\\
\end{itemize}

\end{frame}

\section{Heur\'istica H\'ibrida com Minera\c c\~ao de Dados -- DM-HH}

\begin{frame}  
\frametitle{Minera\c c\~ao de Dados}
\begin{itemize}
\item Conjunto elite:
\end{itemize}
\begin{columns}[c] % the "c" option specifies center vertical alignment
\column{.7\textwidth} % column designated by a command
\hspace*{2cm}
\begin{figure}[ht]
\centering
\includegraphics[width=.550\textwidth]{dm1.pdf}
\label{fig:graspcusto}
\end{figure}
\column{.3\textwidth}
\end{columns}

\end{frame}  

\begin{frame}  
\frametitle{Minera\c c\~ao de Dados}
\begin{itemize}
\item Conjunto elite:
\end{itemize}

\begin{columns}[c] % the "c" option specifies center vertical alignment
\column{.7\textwidth} % column designated by a command
\hspace*{2cm}
\begin{figure}[ht]
\centering
\includegraphics[width=.550\textwidth]{dm2.pdf}
\label{fig:graspcusto}
\end{figure}
\column{.3\textwidth}
\end{columns}
\begin{block}{Para um suporte minimo = 2 temos:}
\{B , C \} como um conjunto frequente.
\end{block}
\end{frame}  

\begin{frame}  
\frametitle{Minera\c c\~ao de Dados}
\begin{itemize}
\item Conjunto elite:
\end{itemize}
\begin{columns}[c] % the "c" option specifies center vertical alignment
\column{.7\textwidth} % column designated by a command
\hspace*{2cm}
\begin{figure}[ht]
\centering
\includegraphics[width=.550\textwidth]{dm3.pdf}
\label{fig:graspcusto}
\end{figure}
\column{.3\textwidth}
\end{columns}

\end{frame}  


\begin{frame}  
\frametitle{Heur\'istica H\'ibrida com Minera\c c\~ao de Dados -- DM-HH}
\begin{itemize}
\item $k/2$ itera\c c\~oes do GRASP com Path Relinking
\begin{itemize}
\item Constru\c c\~ao
\item Busca Local
\item Path Relinking
\end{itemize}
\item Minera\c c\~ao de dados
\item $k/2$ itera\c c\~oes do GRASP com Path Relinking
\begin{itemize}
\item Constru\c c\~ao Adaptada
\item Busca Local
\item Path Relinking
\end{itemize}
\item P\'os--Otimiza\c c\~ao
\end{itemize}
\end{frame}  


\begin{frame}
\frametitle{Constru\c c\~ao Adaptada}
Constru\c c\~ao Adaptada:\\
\begin{itemize}
\item Adiciona \`a solu\c c\~ao todas as instala\c c\~oes presentes no padr\~ao
\item At\'e completar p instala\c c\~oes:\\
\begin{itemize}
\item Escolhe aleatoriamente $q$ instala\c c\~oes ($q = \lceil log_2(m/p)\rceil$)\\
\item Adiciona \`a solu\c c\~ao a mais lucrativa dessas $q$ instala\c c\~oes
\end{itemize}
~~\\
\end{itemize}

\end{frame}

\section{Resultados Computacionais}
\begin{frame}  
\frametitle{Resultados Computacionais}
\begin{itemize}
\item 3 fam\'ilias de inst\^ancias
\begin{itemize}
\item ORLIB -- 40 inst\^ancias
\item TSP -- 18 inst\^ancias
\item RW -- 45 inst\^ancias
\end{itemize}
\end{itemize}
\begin{itemize}
\item 9 execu\c c\~oes com sementes aleat\'orias diferentes.
\end{itemize}
\begin{itemize}
\item Cada estrat\'egia executou 500 itera\c c\~oes
\end{itemize}
\begin{itemize}
\item Tamanho do conjunto elite = 10
\end{itemize}
\begin{itemize}
\item N\'umero de Padr\~oes = 10
\end{itemize}
\begin{itemize}
\item Suporte M\'inimo = 2
\end{itemize}

\end{frame}  

\begin{frame}[shrink]
\frametitle{Resultados Computacionais}
\begin{table}[htbp]
\caption{Tempo do HH e DM-HH para as inst\^ancias ORLIB}
\scriptsize
% \small
\centering
\begin{tabular}{lrrrrr}
\\
\hline 
\noalign{\smallskip}
& \multicolumn{2}{c}{HH} & \multicolumn{2}{c}{DM-HH}\\
\noalign{\smallskip}
Nome/Clientes/\textit{p} & Tempo(s) & Desvio Padr\~ao & Tempo(s) & Desvio Padr\~ao & \% \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
pmed01/100/5 &       0.62 &       0.04 & {\bf 0.61} &       0.04 &       1.08 \\
pmed02/100/10 &       0.51 &       0.03 & {\bf 0.41} &       0.02 &      20.35 \\
pmed03/100/10 &       0.51 &       0.02 & {\bf 0.39} &       0.02 &      23.14 \\
pmed04/100/20 &       0.42 &       0.02 & {\bf 0.34} &       0.07 &      17.65 \\
pmed05/100/33 &       0.40 &       0.03 & {\bf 0.28} &       0.02 &      29.13 \\
pmed06/200/5 &       2.26 &       0.15 & {\bf 2.23} &       0.09 &       1.38 \\
pmed07/200/10 &       1.53 &       0.04 & {\bf 1.08} &       0.11 &      29.36 \\
pmed08/200/20 &       1.19 &       0.02 & {\bf 0.84} &       0.05 &      29.53 \\
pmed09/200/40 &       1.14 &       0.02 & {\bf 0.80} &       0.02 &      30.10 \\
pmed10/200/67 &       1.11 &       0.03 & {\bf 0.79} &       0.02 &      28.41 \\
pmed11/300/5 &       3.86 &       0.13 & {\bf 3.18} &       0.12 &      17.67 \\
pmed12/300/10 &       3.07 &       0.12 & {\bf 2.96} &       0.10 &       3.40 \\
pmed13/300/30 &       2.11 &       0.07 & {\bf 1.46} &       0.06 &      30.89 \\
pmed14/300/60 &       2.14 &       0.03 & {\bf 1.45} &       0.04 &      32.47 \\
pmed15/300/100 &       2.43 &       0.04 & {\bf 1.72} &       0.11 &      29.07 \\
pmed16/400/5 &       7.89 &       0.28 & {\bf 6.76} &       0.08 &      14.28 \\
pmed17/400/10 &       5.65 &       0.11 & {\bf 4.28} &       0.08 &      24.29 \\
pmed18/400/40 &       3.73 &       0.28 & {\bf 2.42} &       0.08 &      35.32 \\
pmed19/400/80 &       3.68 &       0.05 & {\bf 2.49} &       0.05 &      32.39 \\
pmed20/400/133 &       4.20 &       0.11 & {\bf 3.03} &       0.05 &      27.75 \\

\hline
\end{tabular}
\label{tab:ORLIBTime}
\end{table}
\end{frame}

\begin{frame}[shrink]
\frametitle{Resultados Computacionais}
\begin{table}[htbp]
\caption{Tempo do HH e DM-HH para as inst\^ancias ORLIB (cont.)}
\scriptsize
% \small
\centering
\begin{tabular}{lrrrrr}
\\
\hline 
\noalign{\smallskip}
& \multicolumn{2}{c}{HH} & \multicolumn{2}{c}{DM-HH}\\
\noalign{\smallskip}
Nome/Clientes/\textit{p} & Tempo(s) & Desvio Padr\~ao & Tempo(s) & Desvio Padr\~ao & \% \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
pmed21/500/5 &      11.11 &       0.34 & {\bf 10.95} &       0.35 &       1.45 \\
pmed22/500/10 &       9.02 &       0.15 & {\bf 6.97} &       0.15 &      22.70 \\
pmed23/500/50 &       4.93 &       0.20 & {\bf 3.22} &       0.18 &      34.69 \\
pmed24/500/100 &       5.40 &       0.08 & {\bf 3.73} &       0.06 &      30.93 \\
pmed25/500/167 &       6.54 &       0.21 & {\bf 4.76} &       0.09 &      27.22 \\
pmed26/600/5 &      18.05 &       0.25 & {\bf 13.54} &       0.47 &      24.99 \\
pmed27/600/10 &      14.69 &       0.45 & {\bf 11.62} &       0.86 &      20.90 \\
pmed28/600/60 &       7.01 &       0.16 & {\bf 5.26} &     0.20 &      24.96 \\
pmed29/600/120 &       8.38 &       0.32 & {\bf 5.76} &       0.16 &      31.26 \\
pmed30/600/200 &      10.89 &       0.32 & {\bf 7.67} &       0.12 &      29.57 \\
pmed31/700/5 &      26.32 &       0.29 & {\bf 19.76} &       0.58 &      24.92 \\
pmed32/700/10 &      17.86 &       0.51 & {\bf 11.62} &       0.34 &      34.94 \\
pmed33/700/70 &      10.43 &       0.26 & {\bf 6.72} &       0.22 &      35.57 \\
pmed34/700/140 &      12.44 &       0.83 & {\bf 8.26} &       0.16 &      33.60 \\
pmed35/800/5 &      33.73 &       0.77 & {\bf 27.61} &       0.51 &      18.14 \\
pmed36/800/10 &      24.87 &       0.47 & {\bf 19.09} &       0.34 &      23.24 \\
pmed37/800/80 &      14.54 &       0.24 & {\bf 9.18} &       0.59 &      36.86 \\
pmed38/900/5 &      51.08 &       0.74 & {\bf 40.21} &       0.52 &      21.28 \\
pmed39/900/10 &      28.90 &       0.53 & {\bf 19.56} &       0.32 &      32.32 \\
pmed40/900/90 &      19.79 &       0.40 & {\bf 12.80} &       0.34 &      35.32 \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
 M\'edia &  &  &  &  &  25.06 \\
\noalign{\smallskip}
\hline
\end{tabular}
\label{tab:ORLIBTime}
\end{table}
\end{frame}

\begin{frame}[shrink]
\frametitle{Resultados Computacionais}
\begin{table}[!tbp]
\caption{Tempo do HH e DM-HH para as inst\^ancias RW}
\scriptsize
% \small
\centering
\begin{tabular}{lrrrrr}
\\
\hline 
\noalign{\smallskip}
& \multicolumn{2}{c}{HH} & \multicolumn{2}{c}{DM-HH}\\
\noalign{\smallskip}
Classe/Clientes/\textit{p} & Tempo(s) & Desvio Padr\~ao & Tempo(s) & Desvio Padr\~ao & \% \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
 RW/100/10 &       0.99 &       0.04 & {\bf 0.76} &       0.04 &      22.66 \\
 RW/100/20 &       0.62 &       0.08 & {\bf 0.42} &       0.02 &      31.29 \\
 RW/100/30 &       0.44 &       0.02 & {\bf 0.32} &       0.02 &      28.46 \\
 RW/100/40 &       0.40 &       0.03 & {\bf 0.31} &       0.02 &      23.76 \\
 RW/100/50 &       0.33 &       0.02 & {\bf 0.28} &       0.02 &      16.94 \\
 RW/250/10 &       7.61 &       0.28 & {\bf 6.00} &       0.17 &      21.08 \\
 RW/250/25 &       3.89 &       0.05 & {\bf 2.65} &       0.05 &      31.74 \\
 RW/250/50 &       2.33 &       0.07 & {\bf 1.57} &       0.04 &      32.35 \\
 RW/250/75 &       1.84 &       0.04 & {\bf 1.21} &       0.03 &      34.08 \\
 RW/250/100 &       1.65 &       0.03 & {\bf 1.15} &       0.04 &      30.22 \\
 RW/250/125 &       1.40 &       0.05 & {\bf 1.06} &       0.03 &      23.89 \\
 RW/500/10 &      35.91 &       0.67 & {\bf 30.44} &       0.57 &      15.24 \\
 RW/500/25 &      20.02 &       0.43 & {\bf 14.72} &       0.94 &      26.45 \\
 RW/500/50 &      10.26 &       0.20 & {\bf 7.16} &       0.25 &      30.21 \\
 RW/500/75 &       7.76 &       0.12 & {\bf 5.12} &       0.64 &      34.00 \\
 RW/500/100 &       7.23 &       0.70 & {\bf 4.61} &       0.16 &      36.21 \\
 RW/500/150 &       6.60 &       0.39 & {\bf 4.08} &       0.07 &      38.14 \\
 RW/500/200 &       6.56 &       0.25 & {\bf 4.50} &       0.24 &      31.42 \\
 RW/500/250 &       5.19 &       0.12 & {\bf 3.91} &       0.15 &      24.73 \\
 RW/1000/10 &     181.50 &      35.39 & {\bf 125.97} &       2.90 &      30.59 \\
 RW/1000/25 &     116.02 &      19.43 & {\bf 83.25} &       3.48 &      28.25 \\
 RW/1000/50 &      61.50 &       0.72 & {\bf 47.53} &       2.20 &      22.70 \\
 RW/1000/75 &      45.49 &       1.70 & {\bf 32.43} &       1.35 &      28.70 \\\hline
\end{tabular}
\label{tab:RWTime}
\end{table}
\end{frame}

\begin{frame}[shrink]
\frametitle{Resultados Computacionais}
\begin{table}[!tbp]
\caption{Tempo do HH e DM-HH para as inst\^ancias RW (cont.)}
\scriptsize
% \small
\centering
\begin{tabular}{lrrrrr}
\\
\hline 
\noalign{\smallskip}
& \multicolumn{2}{c}{HH} & \multicolumn{2}{c}{DM-HH}\\
\noalign{\smallskip}
Classe/Clientes/\textit{p} & Tempo(s) & Desvio Padr\~ao & Tempo(s) & Desvio Padr\~ao & \% \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
 RW/1000/100 &      40.52 &       1.61 & {\bf 26.71} &       1.12 &      34.08 \\
 RW/1000/200 &      37.90 &       0.58 & {\bf 24.29} &       1.29 &      35.89 \\
 RW/1000/300 &      36.68 &       0.17 & {\bf 23.64} &       0.33 &      35.56 \\
 RW/1000/400 &      40.83 &       2.88 & {\bf 26.33} &       0.24 &      35.51 \\
 RW/1000/500 &      30.69 &       0.27 & {\bf 21.56} &       0.29 &      29.73 \\
 RW/1500/10 &     438.32 &       7.73 & {\bf 358.80} &       6.90 &      18.14 \\
 RW/1500/25 &     268.78 &       7.33 & {\bf 213.17} &       9.10 &      20.69 \\
 RW/1500/50 &     165.73 &       3.28 & {\bf 127.17} &       6.46 &      23.26 \\
 RW/1500/75 &     114.82 &       0.98 & {\bf 90.74} &      13.65 &      20.98 \\
 RW/1500/100 &      99.12 &      10.74 & {\bf 70.30} &       3.15 &      29.07 \\
 RW/1500/250 &      85.34 &       0.92 & {\bf 54.70} &       4.39 &      35.90 \\
 RW/1500/500 &      89.93 &       0.21 & {\bf 57.23} &       0.33 &      36.36 \\
 RW/1500/750 &      72.81 &       0.20 & {\bf 51.88} &       0.26 &      28.75 \\
 RW/2000/10 &     830.56 &      35.49 & {\bf 725.40} &      28.33 &      12.66 \\
 RW/2000/25 &     523.63 &      11.75 & {\bf 433.63} &      15.92 &      17.19 \\
 RW/2000/50 &     360.63 &      12.40 & {\bf 278.68} &      15.15 &      22.73 \\
 RW/2000/75 &     240.66 &       5.66 & {\bf 180.77} &       6.36 &      24.88 \\
 RW/2000/100 &     189.47 &       4.75 & {\bf 142.00} &       6.59 &      25.05 \\
 RW/2000/250 &     148.36 &      11.37 & {\bf 94.12} &       7.86 &      36.56 \\
 RW/2000/500 &     153.68 &       3.30 & {\bf 95.02} &       2.26 &      38.17 \\
 RW/2000/750 &     182.84 &      22.41 & {\bf 115.27} &       2.39 &      36.96 \\
 RW/2000/1000 &     132.88 &       0.29 & {\bf 92.63} &       3.23 &      30.29 \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
 M\'edia &  &  &  &  &  28.26 \\
\noalign{\smallskip}
\hline
\end{tabular}
\label{tab:RWTime}
\end{table}
\end{frame}

\begin{frame}[shrink]
\frametitle{Resultados Computacionais}

\begin{table}[!tbp]
\caption{Tempo do HH e DM-HH para as inst\^ancias FL1400}
%\scriptsize
% \small
\centering
\begin{tabular}{lrrrrr}
\\
\hline 
\noalign{\smallskip}
& \multicolumn{2}{c}{HH} & \multicolumn{2}{c}{DM-HH}\\
\noalign{\smallskip}
Classe/Clientes/\textit{p} & Tempo(s) & Desvio Padr\~ao & Tempo(s) & Desvio Padr\~ao & \% \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
 FL/1400/10 &     155.05 &       5.51 & {\bf 120.78} &       3.78 &      22.10 \\
 FL/1400/20 &     103.13 &       3.41 & {\bf 70.79} &       1.97 &      31.36 \\
 FL/1400/30 &     105.19 &       2.67 & {\bf 65.67} &       1.42 &      37.57 \\
 FL/1400/40 &      93.92 &       2.17 & {\bf 64.76} &       1.99 &      31.05 \\
 FL/1400/50 &      77.66 &       1.29 & {\bf 49.60} &       1.04 &      36.13 \\
 FL/1400/60 &      76.28 &       1.37 & {\bf 54.31} &       2.17 &      28.80 \\
 FL/1400/70 &      65.84 &       1.20 & {\bf 40.97} &       1.00 &      37.78 \\
 FL/1400/80 &      66.35 &       1.85 & {\bf 42.61} &       1.45 &      35.77 \\
 FL/1400/90 &      61.96 &       2.05 & {\bf 38.34} &       1.53 &      38.13 \\
 FL/1400/100 &      62.62 &       1.87 & {\bf 46.11} &       0.61 &      26.36 \\
 FL/1400/150 &      63.00 &       1.35 & {\bf 51.59} &       1.69 &      18.12 \\
 FL/1400/200 &      61.79 &       0.78 & {\bf 43.41} &       3.19 &      29.75 \\
 FL/1400/250 &      70.98 &       2.24 & {\bf 47.72} &       3.17 &      32.78 \\
 FL/1400/300 &      75.40 &       2.35 & {\bf 52.50} &       2.71 &      30.37 \\
 FL/1400/350 &      77.13 &       2.30 & {\bf 57.20} &       3.49 &      25.83 \\
 FL/1400/400 &      77.62 &       1.81 & {\bf 54.95} &       3.87 &      29.20 \\
 FL/1400/450 &      84.72 &       2.39 & {\bf 65.67} &       2.17 &      22.48 \\
 FL/1400/500 &      93.48 &       5.76 & {\bf 68.27} &       3.07 &      26.97 \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
 M\'edia &  &  &  &  &  30.03 \\
\noalign{\smallskip}
\hline
\end{tabular}
\label{tab:FLTime}
\end{table}

\end{frame}  


\begin{frame}[shrink]
\frametitle{Resultados Computacionais}
\begin{table}[htbp]
\caption{HH e DM-HH para as inst\^ancias RW}
\scriptsize
% \small
\centering
\begin{tabular}{lrrrrr}
\\
\hline 
\noalign{\smallskip}
& & \multicolumn{2}{c}{HH} & \multicolumn{2}{c}{DM-HH}\\
\noalign{\smallskip}
Classe/Clientes/\textit{p} & Melhor Conhecida & Melhor & M\'edia & Melhor & M\'edia\\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
 RW/100/10 &        530 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/100/20 &        277 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/100/30 &        213 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/100/40 &        187 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/100/50 &        172 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/250/10 &       3691 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/250/25 &       1360 &    0.000 & {\bf 0.065} &    0.000 &    0.131 \\
 RW/250/50 &        713 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/250/75 &        523 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/250/100 &        444 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/250/125 &        411 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/500/10 &      16108 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/500/25 &       5681 &    0.000 & {\bf 0.016} &    0.000 &    0.086 \\
 RW/500/50 &       2626 &    0.000 & {\bf 0.131} &    0.000 &    0.161 \\
 RW/500/75 &       1757 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/500/100 &       1379 &    0.000 & {\bf 0.056} &    0.000 &    0.064 \\
 RW/500/150 &       1024 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/500/200 &        893 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/500/250 &        833 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/1000/10 &      67811 &    0.000 & {\bf 0.000} &    0.000 &    0.107 \\
 RW/1000/25 &      24896 &    0.108 &    0.162 & {\bf 0.000} & {\bf 0.096} \\
 RW/1000/50 &      11274 &    0.053 &    0.316 & {\bf 0.000} & {\bf 0.203} \\
 RW/1000/75 &       7135 &    0.477 &    0.662 & {\bf 0.000} & {\bf 0.442} \\
\hline
\end{tabular}
\label{tab:RWCost}
\end{table}
\end{frame}

\begin{frame}[shrink]
\frametitle{Resultados Computacionais}
\begin{table}[htbp]
\caption{HH e DM-HH para as inst\^ancias RW (cont.)}
\scriptsize
% \small
\centering
\begin{tabular}{lrrrrr}
\\
\hline 
\noalign{\smallskip}
& & \multicolumn{2}{c}{HH} & \multicolumn{2}{c}{DM-HH}\\
\noalign{\smallskip}
Classe/Clientes/\textit{p} & Melhor Conhecida & Melhor & M\'edia & Melhor & M\'edia\\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
 RW/1000/100 &       5218 & {\bf 0.000} &    0.290 &    0.038 & {\bf 0.200} \\
 RW/1000/200 &       2704 &    0.000 & {\bf 0.033} &    0.000 &    0.049 \\
 RW/1000/300 &       2018 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/1000/400 &       1734 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/1000/500 &       1614 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/1500/10 &     160327 &    0.000 &    0.003 &    0.000 & {\bf 0.000} \\
 RW/1500/25 &      59374 &    0.125 &    0.246 & {\bf 0.000} & {\bf 0.207} \\
 RW/1500/50 &      26912 &    0.305 &    0.598 & {\bf 0.000} & {\bf 0.469} \\
 RW/1500/75 &      16921 & {\bf 0.000} &    0.470 &    0.018 & {\bf 0.188} \\
 RW/1500/100 &      12243 &    0.335 &    0.573 & {\bf 0.000} & {\bf 0.324} \\
 RW/1500/250 &       4761 & {\bf 0.000} &    0.173 &    0.042 & {\bf 0.142} \\
 RW/1500/500 &       2867 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/1500/750 &       2422 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/2000/10 &     293073 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/2000/25 &     109481 &    0.068 &    0.593 & {\bf 0.000} & {\bf 0.241} \\
 RW/2000/50 &      50113 & {\bf 0.000} &    0.583 &    0.010 & {\bf 0.411} \\
 RW/2000/75 &      31463 &    0.372 &    0.760 & {\bf 0.000} & {\bf 0.527} \\
 RW/2000/100 &      22514 &    0.355 &    0.794 & {\bf 0.000} & {\bf 0.432} \\
 RW/2000/250 &       8204 &    0.098 & {\bf 0.274} & {\bf 0.000} &    0.288 \\
 RW/2000/500 &       4479 &    0.022 &    0.057 & {\bf 0.000} & {\bf 0.042} \\
 RW/2000/750 &       3560 &    0.000 &    0.000 &    0.000 &    0.000 \\
 RW/2000/1000 &       3225 &    0.000 &    0.000 &    0.000 &    0.000 \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
\multicolumn{2}{c}{M\'edia} &    0.051 &    0.152 & {\bf 0.002} & {\bf 0.107} \\
\noalign{\smallskip}
\hline
\end{tabular}
\label{tab:RWCost}
\end{table}
\end{frame}

\begin{frame}[shrink]
\frametitle{Resultados Computacionais}

\begin{table}[!tbp]
\caption{HH e DM-HH para as inst\^ancias FL1400}
%\scriptsize
% \small
\centering
\begin{tabular}{lrrrrr}
\\
\hline 
\noalign{\smallskip}
& & \multicolumn{2}{c}{HH} & \multicolumn{2}{c}{DM-HH}\\
\noalign{\smallskip}
Classe/Clientes/\textit{p} & Melhor Conhecido & Melhor & M\'edia & Melhor & M\'edia\\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
 FL/1400/10 &  101249.47 &    0.000 &    0.000 &    0.000 &    0.000 \\
 FL/1400/20 &   57857.55 &    0.001 &    0.001 &    0.001 &    0.001 \\
 FL/1400/30 &   44013.48 &    0.000 &    0.000 &    0.000 &    0.000 \\
 FL/1400/40 &   35002.52 &    0.000 &    0.000 &    0.000 &    0.000 \\
 FL/1400/50 &   29089.78 &    0.002 &    0.002 &    0.002 &    0.002 \\
 FL/1400/60 &   25161.12 &    0.000 &    0.002 &    0.000 & {\bf 0.000} \\
 FL/1400/70 &   22125.53 &    0.002 &    0.002 &    0.002 &    0.002 \\
 FL/1400/80 &   19870.85 &    0.000 & {\bf 0.001} &    0.000 &    0.012 \\
 FL/1400/90 &   17987.94 &    0.004 &    0.004 &    0.004 &    0.004 \\
 FL/1400/100 &    16551.2 &    0.006 &    0.019 &    0.006 & {\bf 0.014} \\
 FL/1400/150 &   12026.43 & {\bf 0.000} &    0.029 &    0.000 & {\bf 0.018} \\
 FL/1400/200 &    9357.74 &    0.011 & {\bf 0.028} & {\bf 0.000} &    0.028 \\
 FL/1400/250 &     7739.8 & {\bf 0.000} & {\bf 0.032} &    0.023 &    0.057 \\
 FL/1400/300 &    6620.92 & {\bf 0.001} & {\bf 0.048} &    0.014 &    0.067 \\
 FL/1400/350 &    5720.88 & {\bf 0.000} & {\bf 0.048} &    0.019 &    0.076 \\
 FL/1400/400 &    5006.75 &    0.000 &    0.013 &    0.000 & {\bf 0.009} \\
 FL/1400/450 &    4468.31 & {\bf 0.000} & {\bf 0.062} &    0.037 &    0.095 \\
 FL/1400/500 &    4046.16 & {\bf 0.000} & {\bf 0.039} &    0.001 &    0.049 \\
\noalign{\smallskip}
\hline
\noalign{\smallskip}
\multicolumn{2}{c}{M\'edia}   & {\bf 0.001} & {\bf 0.018} &    0.006 &    0.024 \\
\noalign{\smallskip}
\hline
\end{tabular}
\label{tab:FLCost}
\end{table}
\end{frame}

\section{An\'alise de Comportamento}

\begin{frame}%[shrink]
\frametitle{An\'alise de Comportamento}
\begin{figure}[ht]
\small
\centering
\caption{Qualidade $\times$ Itera\c c\~ao de uma execu\c c\~ao do HH para rw1000-p25}
\includegraphics[width=.85\textwidth]{custopit-hh.pdf}
\label{fig:graspcusto}
\end{figure}
\end{frame}

\begin{frame}%[shrink]
\frametitle{An\'alise de Comportamento}
\begin{figure}[ht]
\small
\centering
\caption{Qualidade $\times$ Itera\c c\~ao de uma execu\c c\~ao do DM-HH para rw1000-p25}
\includegraphics[width=.85\textwidth]{custopit-dm.pdf}
\label{fig:graspcusto}
\end{figure}
\end{frame}

\begin{frame}%[shrink]
\frametitle{An\'alise de Comportamento}
\begin{figure}[ht]
\small
\centering
\caption{Tempo $\times$ Itera\c c\~ao de uma execu\c c\~ao do HH para rw1000-p25}
\includegraphics[width=.85\textwidth]{tempopit-hh.pdf}
\label{fig:graspcusto}
\end{figure}
\end{frame}

\begin{frame}%[shrink]
\frametitle{An\'alise de Comportamento}
\begin{figure}[ht]
\small
\centering
\caption{Tempo $\times$ Itera\c c\~ao de uma execu\c c\~ao do DM-HH para rw1000-p25}
\includegraphics[width=.85\textwidth]{tempopit-dm.pdf}
\label{fig:graspcusto}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{An\'alise de Comportamento}
\begin{table}[ht]
\caption{Valores m\'edios dos custos} 
%\scriptsize
\centering
\begin{tabular}{rrrr}
\\
\hline
& Constru\c c\~ao & Busca Local & Path-relinking\\
\hline
Primeiras 250 itera\c c\~oes &  33675.70 &  26555.27 & 25846.06 \\
Pr\'oximas 250 itera\c c\~oes &  29007.49 &  25352.95 & 25276.90 \\
\hline
\end{tabular}  
\label{tabavcost}
\end{table}

\begin{table}[ht]
\caption{Tempo computacional m\'edio} 
%\scriptsize
\centering
\begin{tabular}{rrrr}
\\
\hline
 & Constru\c c\~ao & Busca Local & Path-relinking\\
\hline
Primeiras 250 itera\c c\~oes &  7.66 &  101.82 & 105.45 \\
Pr\'oximas 250 itera\c c\~oes &  3.95 &   51.95 & 82.83  \\
\hline
\end{tabular} 
\label{tabavtime} 
\end{table}
\end{frame}

\begin{frame}%[shrink]
\frametitle{An\'alise de Comportamento}
\begin{figure}[ht]
\small
\centering
\caption{An\'alise de converg\^encia para um alvo f\'acil para rw1000-p25}
\includegraphics[width=.85\textwidth]{tempoalvoit-rw1000-p25-facil.pdf}
\label{fig:graspcusto}
\end{figure}
\end{frame}


\begin{frame}%[shrink]
\frametitle{An\'alise de Comportamento}
\begin{figure}[ht]
\small
\centering
\caption{An\'alise de converg\^encia para um alvo dif\'icil para rw1000-p25}
\includegraphics[width=.85\textwidth]{tempoalvoit-rw1000-p25-dificil.pdf}
\label{fig:graspcusto}
\end{figure}
\end{frame}

\begin{frame}%[shrink]
\frametitle{An\'alise de Comportamento}
\begin{figure}[ht]
\small
\centering
\caption{Time-to-target plot para um alvo f\'acil para rw1000-p25}
\includegraphics[width=.85\textwidth]{ttt-plot_rw1000-p25_facil.pdf}
\label{fig:graspcusto}
\end{figure}
\end{frame}



\begin{frame}%[shrink]
\frametitle{An\'alise de Comportamento}
\begin{figure}[ht]
\small
\centering
\caption{Time-to-target plot para um alvo dif\'icil para rw1000-p25}
\includegraphics[width=.85\textwidth]{ttt-plot_rw1000-p25_dificil.pdf}
\label{fig:graspcusto}
\end{figure}
\end{frame}

\section{Conclus\~oes}
\begin{frame}  
\frametitle{Conclus\~oes}
\begin{itemize}
\item Minera\c c\~ao de dados conseguiu tornar a heur\'istica HH mais r\'apida:
\begin{itemize}
\item DM-HH \'e em m\'edia 27,32\% mais r\'apido
\item A qualidade das solu\c c\~oes \'e semelhante
\end{itemize}
\end{itemize}
\begin{itemize}
\item N\~ao s\'o o GRASP simples, mas heur\'isticas mais sofisticadas tamb\'em podem se beneficiar da Minera\c c\~ao de Dados
\end{itemize}
\end{frame}  

\begin{frame}  
\frametitle{Fim}
Obrigado!
\end{frame}
\end{document}
